/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 * 分四种情况，
 * 1.root是null或者root等于p或q，说明root是p，q的公共祖先，
 * 2.递归左右子树，如果左右子树递归函数返回的都不为空，则root就是p，q的公共祖先，
 * 3.左子树递归函数返回的值为空，则p，q都在右子树，
 * 4.右子树递归函数返回的值为空，则p，q都在左子树
 */
 var lowestCommonAncestor = function (root, p, q) {
    const dfs = (root, p, q) => {
      if (!root || root === q || root === p) {
        return root
      }
      let left = dfs(root.left, p, q)
      let right = dfs(root.right, p, q)
  
      if (left !== null && right !== null) return root
      if (left === null) return right
      return left
    }
    return dfs(root, p, q)
  };